package com.base.graph;

import java.util.*;

/**
 * 851. 喧闹和富有
 * 有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
 * <p>
 * 给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自恰（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
 * <p>
 * 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/loud-and-rich
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月15日 12:22
 */
public class LoudAndRich {
    /**
     * 广度优先搜索
     *
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        List<List<Integer>> edges;

        int n = quiet.length;
        // 初始化邻接表
        edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new LinkedList<>());
        }
        for (int[] e : richer) {
            edges.get(e[1]).add(e[0]);
        }
        int[] answer = new int[n];
        Arrays.fill(answer,-1);
        // 在遍历过程中产生了大量重复计算,将已经计算的结果保存下来，遇到就直接取用，不用在重复计算
        for (int i = 0; i < n; i++) {
            // 初始化答案
            answer[i] = i;
            // 队列用于广度优先搜索
            Queue<Integer> queue = new LinkedList<>();

            for (int e : edges.get(i)) {
                // answer[e] > -1表示当前子结点已经被遍历
                if (answer[e] > -1) {
                    answer[i] = quiet[answer[i]]>quiet[answer[e]]?answer[e]:answer[i];
                }else {
                    queue.add(e);
                }
            }
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                if (quiet[poll] < quiet[answer[i]]) {
                    answer[i] = poll;
                }
                for (int e : edges.get(poll)) {
                    // answer[e] > -1表示当前子结点已经被遍历
                    if (answer[e] > -1) {
                        answer[i] = quiet[answer[i]]>quiet[answer[e]]?answer[e]:answer[i];
                    }else {
                        queue.add(e);
                    }
                }
            }
        }

        return answer;
    }

    /**
     * 深度优先搜索试试
     *
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich1(int[][] richer, int[] quiet) {
        List<List<Integer>> edges;

        int n = quiet.length;
        // 初始化邻接表
        edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edges.add(new LinkedList<>());
        }
        for (int[] e :
                richer) {
            edges.get(e[1]).add(e[0]);
        }

        int[] answer = new int[n];
        Arrays.fill(answer,-1);
        for (int i = 0; i < n; i++) {
            dfs(i,answer,edges,quiet);
        }

        return answer;
    }

    private void dfs(int i,int[] answer, List<List<Integer>> edges,int[] quiet){

        if(answer[i]>-1){
            return;
        }
        answer[i] = i;
        for (int e:edges.get(i)){
            dfs(e,answer,edges,quiet);
            if(quiet[answer[i]]>quiet[answer[e]]){
                answer[i] = answer[e];
            }
        }
    }

}
